class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

    def _pre_order(self):
        if not self:
            return ""
        res = str(self.val)
        if self.left:
            res += self.left._pre_order()
        if self.right:
            res += self.right._pre_order()
        return res

    def _in_order(self):
        if not self:
            return ""
        res = ""
        if self.left:
            res += self.left._in_order()
        res += str(self.val)
        if self.right:
            res += self.right._in_order()
        return res

    def _post_order(self):
        if not self:
            return ""
        res = ""
        if self.left:
            res += self.left._post_order()
        if self.right:
            res += self.right._post_order()
        res += str(self.val)
        return res

    def order(self, mode="pre_order"):
        """the string when call print(TreeNOde).

        Args:
            mode: must be one of those:
            ["pre_order","in_order","post_order"]
        """
        tmp_str = "#"
        if mode == "pre_order":
            tmp_str += self._pre_order()
        elif mode == "in_order":
            tmp_str += self._in_order()
        elif mode == "post_order":
            tmp_str += self._post_order()
        else:
            raise ValueError(r"mode must be in [pre_order,in_order,post_order]")
        return tmp_str


def build_tree(middle: str, last: str) -> TreeNode:
    if middle == "":
        return None
    root_val = last[-1]
    root_index_in_middle = middle.index(root_val)
    root = TreeNode(root_val)
    root.left = build_tree(middle[0:root_index_in_middle], last[0:root_index_in_middle])
    root.right = build_tree(
        middle[root_index_in_middle + 1 :], last[root_index_in_middle:-1]
    )

    return root


def first_search(root):
    if not root:
        return None
    print(root.val, end="")
    first_search(root.left)
    first_search(root.right)
    return


if __name__ == "__main__":
    """
    给出一个二叉树的中序遍历以及后序遍历值，求这个二叉树的先序遍历。
    思路：通过中序遍历和后序遍历建立二叉树，然后进行简单的先序遍历就行了。
    """
    middle_sequence = "DGFHBAEC"
    last_sequence = "GHFDBECA"
    root = build_tree(middle_sequence, last_sequence)
    print(root.order(mode="post_order"))
